Perfect codes in circulant graphs

Abstract

A perfect code in a graph Γ=(V,E) is a subset C of V that is an independent set such that every vertex in V∖C is adjacent to exactly one vertex in C. A total perfect code in Γ is a subset C of V such that every vertex of V is adjacent to exactly one vertex in C. A perfect code in the Hamming graph H(n,q) agrees with a q-ary perfect 1-code of length n in the classical setting. In this paper we give a necessary and sufficient condition for a circulant graph of degree p−1 to admit a perfect code, where p is an odd prime. We also obtain a necessary and sufficient condition for a circulant graph of order n and degree pl−1 to have a perfect code, where p is a prime and pl the largest power of p di..